package FINAL.find_rumors;

import java.util.LinkedList;
import java.util.Queue;

public class Calculaotr_distance {
	/**
	 * 
	 * @param index
	 *            tính từ đỉnh có id là index
	 * @param list
	 *            ma trận hai chiều biễu diễn đồ thị
	 * @param list_gs
	 *            mảng id của tập node giám sát
	 * @return mảng chưa khoảng cách từ đỉnh index đến tất cả các đỉnh của tập
	 *         giám sát, nếu không có đường đến monitor đó thì giá trị bằng -1
	 */
	public static int[] kc_den_tap_gs(int index, int[][] list, int[] list_gs) {

		int[] kq_kc = new int[list_gs.length];
		for (int i = 0; i < list_gs.length; i++) {
			// System.out.println("\nDuong di tu: " + index + " den " +
			// list_gs[i]);
			int[] pre = A(index, list);
			int count_hops = 1;
			int tmp = list_gs[i];
			// System.out.print(tmp + "<-");
			while (pre[tmp] != index) {
				// System.out.print(tmp + "<-");
				count_hops++;
				tmp = pre[tmp];
				if (tmp == -1) {
					count_hops = -1;
					// System.out.println("KOKOKO");
					break;
				}
			}
			kq_kc[i] = count_hops;
			// System.out.print(count_hops);
		}
		return kq_kc;
	}

	/**
	 * 
	 * @param index
	 *            tính từ đỉnh có id là index
	 * @param list
	 *            ma trận hai chiều biễu diễn đồ thị
	 * @param list_gs
	 *            mảng id của tập node giám sát
	 * @return một giá trị là khoảng tổng khoảng cách từ node index đến tất cả
	 *         node của tập gs. Nếu với một node giám sát mà ko tồn tại đường đi
	 *         thì sẽ return khoảng cách bằng -1 luôn
	 */
	public static int tinh_kc_den_tap_gs(int index, int[][] list, int[] list_gs) {
		int[] ketqua = kc_den_tap_gs(index, list, list_gs);
		int tong = 0;
		for (int i = 0; i < ketqua.length; i++) {
			if (ketqua[i] == -1) {
				return -1;
			} else {
				tong += ketqua[i];
			}
		}
		return tong;
	}

	public static int[][] tinh_kc_den_tap_gs_all(int[][] list, int[] list_gs) {
		int[][] kc = new int[2][7500];
		for (int i = 0; i < 7500; i++) {
			kc[0][i] = i;
			kc[1][i] = 0;
		}

		// tính khoảng cách cho tất cả các node
		int c = 0;
		for (int i = 0; i < 7500; i++) {
			kc[1][i] = tinh_kc_den_tap_gs(i, list, list_gs);
			c++;
			// System.err.println("thêm 1 node: "+c);
		}

		// Sắp xếp lại hai mảng kc và kq
		for (int i = 0; i < 7500; i++) {
			for (int j = i + 1; j < 7500; j++) {
				if (kc[1][j] > kc[1][i]) {
					int tmp = kc[1][i];
					kc[1][i] = kc[1][j];
					kc[1][j] = tmp;
					// //////
					int tmp2 = kc[0][i];
					kc[0][i] = kc[0][j];
					kc[0][j] = tmp2;
				}
			}
		}
		// for (int i = 0; i < 7500; i++) {
		// System.out.println("node " + kc[0][i] + " có kc: " + kc[1][i]);
		// }
		return kc;
	}

	/**
	 * 
	 * @param index
	 *            id của đỉnh xuất phát
	 * @param list
	 *            ma trận biểu diễn đồ thị
	 * @param end_node
	 *            id của đỉnh cuối
	 * @return giá trị khoảng cách từ đình xuất phát đến đỉnh cuối
	 */
	public static int kc_giua_hai_node(int index, int[][] list, int end_node) {

		// System.out.println("\nDuong di tu: " + index + " den " +
		// list_gs[i]);
		if (index == end_node)
			return 0;
		int[] pre = A(index, list);
		int count_hops = 1;
		int tmp = end_node;
		if (tmp == -1) {
			count_hops = -1;
			return count_hops;
		}
		// System.out.print(tmp + "<-");
		while (pre[tmp] != index) {
			// System.out.print(tmp + "<-");
			count_hops++;
			tmp = pre[tmp];
			if (tmp == -1) {
				count_hops = -1;
				// System.out.println("KO có đường đi giữa hai node" + index
				// + " - " + end_node);
				break;
			}
			// System.out.print(count_hops);
		}
		return count_hops;
	}

	/**
	 * 
	 * @param index
	 *            node xuất phát
	 * @param list
	 *            ma trận biểu diễn đồ thị
	 * @return mảng lưu node liền trước trên đường đi
	 */
	public static int[] A(int index, int[][] list) {
		int[] pre_node = new int[list.length];
		int[] danh_dau = new int[list.length];
		for (int i = 0; i < list.length; i++) {
			pre_node[i] = -1;
			danh_dau[i] = -1;
		}

		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(index);
		danh_dau[index] = 1;

		while (!queue.isEmpty()) {
			int tmp = queue.poll();
			for (int i = 0; i < list.length; i++) {
				if (list[tmp][i] == 1 && danh_dau[i] == -1) {
					queue.add(i);
					danh_dau[i] = 1;
					pre_node[i] = tmp;
				}
			}
		}
		// for (int i = 0; i < 7500; i++) {
		// System.out.println("pre: " + i + "=" + pre_node[i]);
		// }
		return pre_node;
	}

	public static void find_rumors(int[][] list) {

	}
}
